<html lang="en-US">

<head>
    
<title>Go map 如何缩容？ - 花落雨忧</title>

<meta property="og:title" content="Go map 如何缩容？ - 花落雨忧">



    



    
    <meta property="description" content="大家好，我是煎鱼。
前几天看到 Go 圈子的著名股神（不是我&amp;hellip;），在归类中简单的提到了 Go 语言中 map 的缩容的描述，这让我对其产生了兴趣，想要来一探究竟。
我们常常喊扩缩容，扩缩容，但社区里都是清一色分析扩容机制，Go 面试官也都是卷 Go 语言 map 的扩容机制&amp;hellip;
在 Go 语言中的 map 缩容机制是怎么做的呢，今天就由煎鱼带大家一起研讨围观一轮。 &amp;hellip;">
    <meta property="og:description" content="大家好，我是煎鱼。
前几天看到 Go 圈子的著名股神（不是我&amp;hellip;），在归类中简单的提到了 Go 语言中 map 的缩容的描述，这让我对其产生了兴趣，想要来一探究竟。
我们常常喊扩缩容，扩缩容，但社区里都是清一色分析扩容机制，Go 面试官也都是卷 Go 语言 map 的扩容机制&amp;hellip;
在 Go 语言中的 map 缩容机制是怎么做的呢，今天就由煎鱼带大家一起研讨围观一轮。 &amp;hellip;">
    






<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="viewport" content="width=device-width,initial-scale=1">

<link rel="shortcut icon" href="https://www.lican.asia/logo/logo.png" type="image/x-icon" />



<link rel="stylesheet" href="/css/style.min.css" />

<link rel="stylesheet" href="/css/reset.min.css" />




<script src="https://www.lican.asia/js/highlight.min.js"></script>

<script>
hljs.configure({ ignoreUnescapedHTML: true })
hljs.highlightAll();
</script>


<script src="https://www.lican.asia/js/jquery.min.js"></script>




<link href="https://www.lican.asia/css/hugo-code.min.css" rel="stylesheet" />



    <style>
        .post-content img {
            max-width: 400px;
        }
    </style>
</head>

<body id="period" class="home blog">
    <a class="skip-content" href="#main">Press "Enter" to skip to content</a>
    <div id="overflow-container" class="overflow-container">
        <header class="site-header" id="site-header" role="banner">
    <div class="max-width">
        <div id="title-container" class="title-container">
            <div id="site-title" class="site-title"><a href="/">花落雨忧</a></div>
            <p class="tagline">思所及 力所行 方为真.</p>
        </div>
        
        <div id="menu-primary-container" class="menu-primary-container">
            <div class="icon-container">
            </div>
            <div id="menu-primary" class="menu-container menu-primary" role="navigation">
                <nav class="menu">
                    <ul id="menu-primary-items" class="menu-primary-items">
                        
                        
                        <li id="menu-item-0"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/posts" aria-current="page" tabindex="0">首页</a></li>
                        
                        <li id="menu-item-1"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/tech/" aria-current="page" tabindex="1">技术文档</a></li>
                        
                        <li id="menu-item-2"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/article/" aria-current="page" tabindex="2">文章</a></li>
                        
                        <li id="menu-item-3"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/project/" aria-current="page" tabindex="3">项目</a></li>
                        
                        <li id="menu-item-4"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/about/" aria-current="page" tabindex="4">关于</a></li>
                        
                    </ul>
                </nav>
            </div>
        </div>
    </div>
</header>

        <div id="primary-container" class="primary-container">
            <div class="max-width">
                <section id="main" class="main" role="main">
                    <div id="loop-container" class="loop-container">
                        <div
                            class="post type-post status-publish format-standard hentry entry">
                            <article>
                                <div class="post-container">
                                    <div class="post-header">
                                        <h2 class="post-title">
                                            <a href="/posts/posts/go/map-reset/">Go map 如何缩容？</a>
                                        </h2>
                                        
                                        <div class="post-byline">Published on
                                            <a class="date" href="javascript:;">2021/12/31</a>
                                            
                                            
                                            
                                            
                                            
                                        
                                    </div>
                                    <div class="post-content">
                                        <p>大家好，我是煎鱼。</p>
<p>前几天看到 Go 圈子的著名股神（不是我&hellip;），在归类中简单的提到了 Go 语言中 map 的缩容的描述，这让我对其产生了兴趣，想要来一探究竟。</p>
<p>我们常常喊扩缩容，扩缩容，但社区里都是清一色分析扩容机制，Go 面试官也都是卷 Go 语言 map 的扩容机制&hellip;</p>
<p>在 <strong>Go 语言中的 map 缩容机制是怎么做的</strong>呢，今天就由煎鱼带大家一起研讨围观一轮。</p>
<h2 id="基本分析">基本分析</h2>
<p>在 Go 底层源码 src/runtime/map.go 中，扩缩容的处理方法是 grow 为前缀的方法来处理的。</p>
<p>其中扩缩容涉及到的是插入元素的操作，对应 mapassign 方法：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-golang" data-lang="golang"><span style="display:flex;"><span><span style="color:#66d9ef">func</span> <span style="color:#a6e22e">mapassign</span>(<span style="color:#a6e22e">t</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">maptype</span>, <span style="color:#a6e22e">h</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">hmap</span>, <span style="color:#a6e22e">key</span> <span style="color:#a6e22e">unsafe</span>.<span style="color:#a6e22e">Pointer</span>) <span style="color:#a6e22e">unsafe</span>.<span style="color:#a6e22e">Pointer</span> {
</span></span><span style="display:flex;"><span>  <span style="color:#f92672">...</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">growing</span>() <span style="color:#f92672">&amp;&amp;</span> (<span style="color:#a6e22e">overLoadFactor</span>(<span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">count</span><span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>, <span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">B</span>) <span style="color:#f92672">||</span> <span style="color:#a6e22e">tooManyOverflowBuckets</span>(<span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">noverflow</span>, <span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">B</span>)) {
</span></span><span style="display:flex;"><span>		<span style="color:#a6e22e">hashGrow</span>(<span style="color:#a6e22e">t</span>, <span style="color:#a6e22e">h</span>)
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">goto</span> <span style="color:#a6e22e">again</span>
</span></span><span style="display:flex;"><span>	}
</span></span><span style="display:flex;"><span>  <span style="color:#f92672">...</span>
</span></span><span style="display:flex;"><span>}
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">func</span> (<span style="color:#a6e22e">h</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">hmap</span>) <span style="color:#a6e22e">growing</span>() <span style="color:#66d9ef">bool</span> {
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">return</span> <span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">oldbuckets</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">nil</span>
</span></span><span style="display:flex;"><span>}
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">func</span> <span style="color:#a6e22e">overLoadFactor</span>(<span style="color:#a6e22e">count</span> <span style="color:#66d9ef">int</span>, <span style="color:#a6e22e">B</span> <span style="color:#66d9ef">uint8</span>) <span style="color:#66d9ef">bool</span> {
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">return</span> <span style="color:#a6e22e">count</span> &gt; <span style="color:#a6e22e">bucketCnt</span> <span style="color:#f92672">&amp;&amp;</span> uintptr(<span style="color:#a6e22e">count</span>) &gt; <span style="color:#a6e22e">loadFactorNum</span><span style="color:#f92672">*</span>(<span style="color:#a6e22e">bucketShift</span>(<span style="color:#a6e22e">B</span>)<span style="color:#f92672">/</span><span style="color:#a6e22e">loadFactorDen</span>)
</span></span><span style="display:flex;"><span>}
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">func</span> <span style="color:#a6e22e">tooManyOverflowBuckets</span>(<span style="color:#a6e22e">noverflow</span> <span style="color:#66d9ef">uint16</span>, <span style="color:#a6e22e">B</span> <span style="color:#66d9ef">uint8</span>) <span style="color:#66d9ef">bool</span> {
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">B</span> &gt; <span style="color:#ae81ff">15</span> {
</span></span><span style="display:flex;"><span>		<span style="color:#a6e22e">B</span> = <span style="color:#ae81ff">15</span>
</span></span><span style="display:flex;"><span>	}
</span></span><span style="display:flex;"><span>  
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">return</span> <span style="color:#a6e22e">noverflow</span> <span style="color:#f92672">&gt;=</span> uint16(<span style="color:#ae81ff">1</span>)<span style="color:#f92672">&lt;&lt;</span>(<span style="color:#a6e22e">B</span><span style="color:#f92672">&amp;</span><span style="color:#ae81ff">15</span>)
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><p>核心看到针对扩缩容的判断逻辑：</p>
<ul>
<li>当前没有在扩容：条件为 oldbuckets 不为 nil。</li>
<li>是否可以进行扩容：条件为 <code>hmap.count</code>&gt; hash 桶数量 <code>(2^B)*6.5</code>。其中 <code>hmap.count</code> 指的是map 的数据数目， <code>2^B</code> 仅指 hash 数组的大小，不包含溢出桶。</li>
<li>是否可以进行缩容：条件为溢出桶（noverflow）的数量 &gt;= 32768（1&laquo;15）。</li>
</ul>
<p>而我们可以关注到，无论是扩容还是缩容，其都是由 <code>hashGrow</code> 方法进行处理：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-golang" data-lang="golang"><span style="display:flex;"><span><span style="color:#66d9ef">func</span> <span style="color:#a6e22e">hashGrow</span>(<span style="color:#a6e22e">t</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">maptype</span>, <span style="color:#a6e22e">h</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">hmap</span>) {
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">bigger</span> <span style="color:#f92672">:=</span> uint8(<span style="color:#ae81ff">1</span>)
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">overLoadFactor</span>(<span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">count</span><span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>, <span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">B</span>) {
</span></span><span style="display:flex;"><span>		<span style="color:#a6e22e">bigger</span> = <span style="color:#ae81ff">0</span>
</span></span><span style="display:flex;"><span>		<span style="color:#a6e22e">h</span>.<span style="color:#a6e22e">flags</span> <span style="color:#f92672">|=</span> <span style="color:#a6e22e">sameSizeGrow</span>
</span></span><span style="display:flex;"><span>	}
</span></span><span style="display:flex;"><span>  <span style="color:#f92672">...</span>
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><p>若是扩容，则 bigger 为 1，也就是 B+1。代表 hash 表容量扩大 1 倍。不满足就是缩容，也就是 hash 表容量不变。</p>
<p>可以得出结论：map 的<strong>扩缩容的主要区别在于 hmap.B 的容量大小改变</strong>。而缩容由于 hmap.B 压根没变，内存空间的占用也是没有变化的。</p>
<h2 id="带来的隐患">带来的隐患</h2>
<p>这种方式其实是存在运行隐患的，也就是<strong>导致在删除元素时，并不会释放内存，使得分配的总内存不断增加</strong>。如果一个不小心，拿 map 来做大 key/value 的存储，也不注意管理，很容易就内存爆了。</p>
<p>也就是 Go 语言的 map 目前实现的是 ”伪缩容“，仅针对溢出桶过多的情况。若是触发缩容，hash 数组的占用的内存大小不变。</p>
<p>若要实现 ”真缩容“，Go Contributor @josharian 表示目前<strong>唯一可用的解决方法是：创建一个新的 map 并从旧的 map 中复制元素</strong>。</p>
<p>示例如下：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-golang" data-lang="golang"><span style="display:flex;"><span><span style="color:#a6e22e">old</span> <span style="color:#f92672">:=</span> make(<span style="color:#66d9ef">map</span>[<span style="color:#66d9ef">int</span>]<span style="color:#66d9ef">int</span>, <span style="color:#ae81ff">9999999</span>)
</span></span><span style="display:flex;"><span><span style="color:#a6e22e">new</span> <span style="color:#f92672">:=</span> make(<span style="color:#66d9ef">map</span>[<span style="color:#66d9ef">int</span>]<span style="color:#66d9ef">int</span>, len(<span style="color:#a6e22e">old</span>))
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">for</span> <span style="color:#a6e22e">k</span>, <span style="color:#a6e22e">v</span> <span style="color:#f92672">:=</span> <span style="color:#66d9ef">range</span> <span style="color:#a6e22e">old</span> {
</span></span><span style="display:flex;"><span>    <span style="color:#a6e22e">new</span>[<span style="color:#a6e22e">k</span>] = <span style="color:#a6e22e">v</span>
</span></span><span style="display:flex;"><span>}
</span></span><span style="display:flex;"><span><span style="color:#a6e22e">old</span> = <span style="color:#a6e22e">new</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">...</span>
</span></span></code></pre></div><p>无比的像，复制粘贴，大的往小的挪动，再删掉大的就可以了。</p>
<p>果然程序员的解决方案都是相似的。</p>
<h2 id="为什么不支持">为什么不支持</h2>
<p>下述内容会主要基于如下两个 issues 和 proposal 来分析：</p>
<ol>
<li>《<a href="https://github.com/golang/go/issues/20135" title="runtime: shrink map as elements are deleted">runtime: shrink map as elements are deleted</a>》</li>
<li>《<a href="https://github.com/golang/go/issues/45328" title="proposal: runtime: add way to clear and reuse a map's working storage">proposal: runtime: add way to clear and reuse a map&rsquo;s working storage</a>》</li>
</ol>
<p>目前 map 的缩容处理起来比较棘手，最早的 issues 是 2016 年提出的，也有人提过一些提案，但都因为种种原因被拒绝了。</p>
<p>简单来讲，就是没有找到一个很好的方法实现，存在明确的实现成本问题，没法很方便的 ”告诉“ Go 运行时，我要：</p>
<ol>
<li>记得保留存储空间，我要立即重用 map。</li>
<li>赶紧释放存储空间，map 从现在开始会小很多。</li>
</ol>
<p>抽象来看症结是：<strong>需要保证增长结果在下一个开始之前完成</strong>，此处的增长指的是 ”从小到大，从一个大小到相同大小，从大到小“ 的复杂过程。</p>
<p>这属于一个多重 case，从而导致也就一直拖着，慢慢想。</p>
<h2 id="总结">总结</h2>
<p>Go 语言中 map 的扩容机制是大家经常思考和学习的，但是缩容方面现在也是一个大 ”坑“。虽然不误用就没问题。</p>
<p>但是一旦新同学来了，不知道，一塞，就会出问题。我有一个朋友，之前面试时，就听闻有人会塞几个 GB 的数据进 map，可想而知还是很危险的。</p>
<p>现有 map 的缩容机制，是存在短板的，背后有着比较多重的纠结，不知道你<strong>有没有什么好的建议或想法呢，欢迎大家一起来讨论</strong>！</p>


                                        
                                        
                                        
                                        <div class="rp4wp-related-posts">
                                            <h3>相关文章</h3>
                                            <ul>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/map-65/">面试官：为什么 Go 的负载因子是 6.5？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/sync-map/">Go 并发读写 sync.map 的强大之处</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/map-slice-concurrency/">为什么 Go map 和 slice 是非线程安全的？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/gmp-why-p/">经典面试题：你觉得 Go 在什么时候会抢占 P？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/goroutine-leak/">跟面试官聊 Goroutine 泄露的 6 种方法，真刺激！</a>
                                                    </div>
                                                </li>
                                                
                                            </ul>
                                        </div>
                                        
                                        
                                    </div>

                                    
                                    
                                    

                                    
                                    <div class="post-meta">
                                        
                                        
                                        <div class="post-tags">
                                            <ul>
                                            
                                            <li>
                                                <a href="/tags/go" title="View all posts tagged match">go</a>
                                            </li>
                                            
                                            <li>
                                                <a href="/tags/%e9%9d%a2%e8%af%95%e9%a2%98" title="View all posts tagged match">面试题</a>
                                            </li>
                                            
                                            </ul>
                                        </div>
                                        
                                        
                                        <nav class="further-reading">
                                            
                                            <div class="previous">
                                                <span>&lt;&lt; Prev</span>
                                                <a href="https://www.lican.asia/posts/posts/go/map-65/"
                                                    rel="prev">面试官：为什么 Go 的负载因子是 6.5？</a> </div>
                                            
                                            
                                            <div class="next">
                                                <span>Next >></span>
                                                <a href="https://www.lican.asia/posts/posts/go/when-gc/">Go 什么时候会触发 GC？</a> 
                                            </div>
                                            
                                        </nav>
                                    </div>
                                    
                                    

                                    
                                    
                                    

                                </div>
                            </article>
                        </div>
                    </div>
                </section>
                <aside class="sidebar sidebar-primary" id="sidebar-primary" role="complementary">
    <h1 class="screen-reader-text">Sidebar</h1>
    

    
    
    <section id="text-2" class="widget widget_text">
        <div class="textwidget">
            
            <div id="profile">
                <div id="profile_picture"><img src="https://www.lican.asia/logo/logo.png"></div>
                <div id="profile_intro">
                    <p><span class="name">Lican</span></p>
                    <p class="intro">全栈开发者，爱好造轮子。</p>
                </div>
            </div>
            
            <p>
                <script type="text/javascript">
                    (function ($) {
                        $(document).ready(function () {
                            var menuPrimaryContainer = $('#menu-primary-container');
                            var profile = $('#text-2');
                            $('#toggle-navigation').click(function () {
                                if (menuPrimaryContainer.hasClass('open')) {
                                    profile.removeClass('open');
                                } else {
                                    profile.addClass('open');
                                }
                            });
                        });
                    })(jQuery);
                </script>
            </p>
        </div>
    </section>
    
    
    
    
    
    <section id="text-5" class="widget widget_text">
        <h2 class="widget-title">开源项目</h2>
        <div class="textwidget">
            <div id="projects" style="line-height: 22px;">
                
                <a href="https://github.com/idoubi/gonews"
                    target="_blank">gonews</a>: &nbsp;Daily news for golang<br>
                
                <a href="https://github.com/idoubi/sql2struct"
                    target="_blank">sql2struct</a>: &nbsp;Generate go struct according to SQL<br>
                
                <a href="https://github.com/idoubi/goz"
                    target="_blank">goz</a>: &nbsp;Request library used in golang<br>
                
        </div>
    </section>
    
    

    
    
    
    
    <section id="qrcode" class="widget widget_media_image">
        <h2 class="widget-title">微信公众号</h2>
        <img width="258" height="258"
            src="https://www.lican.asia/wechat/lican.png"
            class="image wp-image-5514  attachment-full size-full" alt=""
            style="max-width: 100%; height: auto;"
            sizes="(max-width: 258px) 100vw, 258px">
    </section>
    
    

    
    
    

    
    
    

    
    
    
    
</aside>
            </div>
        </div>

        <footer id="site-footer" class="site-footer" role="contentinfo">
    <div class="max-width">
    </div>
    <div class="footer">
        <div id="footercontent">
            © lican.asia All rights reserved<br/>
            Built with Hugo Theme <a href="https://github.com/idoubi/hugo-theme-period" target="_blank">Period</a>
        </div>
    </div>
</footer>

<script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?e8351b6d4626d5881d439ea1f6184baa";
      var s = document.getElementsByTagName("script")[0]; 
      s.parentNode.insertBefore(hm, s);
    })();
</script>
    
    
    </div>
    
</body>

</html>